package com.base.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

/**
 * TODO(475. 供暖器)
 *
 * @author leon
 * @date 2021年12月20日 14:17
 */
public class FindRadius {
    /**
     * 超出时间限制
     *
     * @param houses
     * @param heaters
     * @return
     */
    public int findRadius(int[] houses, int[] heaters) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < houses.length; i++) {
            set.add(houses[i]);
        }
        int ans = -1;
        int j = -1;
        // 多源遍历
        while (!set.isEmpty()) {
            ans++;
            j++;
            for (int i = 0; i < heaters.length; i++) {
                set.remove(heaters[i] + j);
                set.remove(heaters[i] - j);
                if (set.isEmpty()) {
                    break;
                }
            }

        }
        return ans;
    }

    /**
     * 两层循环，复杂度n2
     *
     * @param houses
     * @param heaters
     * @return
     */
    public int findRadius1(int[] houses, int[] heaters) {
        int ans = 0;

        for (int i = 0; i < houses.length; i++) {
            int min = Math.abs(heaters[0] - houses[i]);
            for (int j = 1; j < heaters.length; j++) {
                min = Math.min(Math.abs(heaters[j] - houses[i]), min);
            }
            ans = Math.max(min, ans);
        }
        return ans;
    }

    /**
     * 二分查找
     * @param houses
     * @param heaters
     * @return
     */
    public int findRadius2(int[] houses, int[] heaters) {
        int ans = 0;
        Arrays.sort(heaters);
        for (int i = 0; i < houses.length; i++) {
            // 找到距离当前点的最短的路径
            int search = search(heaters, houses[i]);
            ans = Math.max(search, ans);
        }
        return ans;
    }

    /**
     * 查找元素target，返回它的位置，如果不存在元素，则返回距离它最近的位置
     *
     * @param heaters
     * @param target
     * @return
     */
    private int search(int[] heaters, int target) {
        int left = 0, right = heaters.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (heaters[mid] == target) {
                break;
            } else if (heaters[mid] < target) {
                left = mid + 1;
            } else if (heaters[mid] > target) {
                right = mid - 1;
            }
        }
        // 可能会数组下标越界
        if (left> heaters.length){
            return Math.abs(target - heaters[right]);
        }
        if(right<0){
            return Math.abs(target - heaters[left]);
        }
        if (left>right){
            return Math.min(Math.abs(heaters[left]-target),Math.abs(target - heaters[right]));
        }
        // 找到了，自然距离就是0
        return 0;

    }

    public static void main(String[] args) {
        System.out.println(new FindRadius().search(new int[]{1,2,5,6},3));
    }
}
